费用报销
题目 费用报销
思路分析
比悲伤还悲伤的故事
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int daysfromstart(int month,int day){
int totaldays=0;
for(int m=1;m<month;m++)
totaldays+=days[m];//告知不是闰年 不需要特判2月
totaldays+=day;
return totaldays;
}
const int N=1010,M=5010;
int f[N][M];//前i个物品中选 总价值不超过j的所有选法的集合 属性max
int n,m,k;
int w[N],d[N];//需要存储每个物品的价值 以及是一年中的第几天
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
int month,day,v;cin>>month>>day>>v;
d[i]=daysfromstart(month,day);
w[i]=v;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// 不选第i个票据的情况
f[i][j] = f[i - 1][j];
// 尝试选第i个票据
if (j >= w[i]) {
for (int p = 0; p < i; p++) {
if (d[p] == 0 || abs(d[i] - d[p]) >= k) {
f[i][j] = max(f[i][j], f[p][j - w[i]] + w[i]);
}
}
}
}
}
cout<<f[n][m];
return 0;
}
搞半天 案例过了 结果全错
唉 可是尽力也只能分析到这里了 确实是有些可惜和后怕
正解是以时间为索引进行dp的
//本题是动态规划的01背包问题,将日期视为体积,报销金额视为价值
//对于第i天,其状态从第i-k天递推而来(i-k>0,否则为0)
//在总报销金额不超过m的情况下,第i天的报销金额可以选择也可以不选
//若选择则为dp[i]+dp[i-k],若不选择则dp[i]=dp[i-1]
//若累加第i天后总报销金额超过了m,则dpi]只能用dp[i-1]更新
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int dp[N];//dp[i]表示截止到本年第i天,所能报销的最大金额
map<pair<int,int>,int>mp;//将<月,日>映射为本年的第几天
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//month[i]存储第i个月的天数(不是闰年)
int n,m,k;
void get_day()//初始化,将本年内的每个日期映射为天数
{
int day=0;
for(int i=1;i<=12;i++)
{
for(int j=1;j<=month[i];j++)
{
day++;
mp[make_pair(i,j)]=day;
}
}
}
int main()
{
get_day();//初始化
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)//输入n个票据
{
int mon,day,value;
scanf("%d%d%d",&mon,&day,&value);//输入月、日和报销金额
int date=mp[make_pair(mon,day)];//获取该<月,日>对应的天数
dp[date]=max(dp[date],value);//第date天的最大报销金额等于同一天内的最大面值的票据
}
for(int i=1;i<=365;i++)//遍历本年度内的每一天
{
int pre=max(0,i-k);//计算上一个能累加报销金额的日期:k天之前(不能小于0)
if(dp[i]+dp[pre]<=m)//若上一次累加上本次的金额不超过m,说明可以累加
{
dp[i]=max(dp[i-1],dp[i]+dp[pre]);
//累加上一次,为dp[i]+dp[pre];
//不累加上一次,为dp[i-1]
//二者取最大值更新dp[i]
}
else dp[i]=dp[i-1];//上一次累加本次的金额已经超过了m,一定不能累加,只能与前一天相同
}
printf("%d\n",dp[365]);//递推完毕,最大报销金额在dp数组的最末尾
return 0;
}
chatgpt:
在您的代码中，存在几个关键的逻辑问题和误解，导致您无法得到正确的结果。这些问题主要集中在如何处理票据的日期差与金额的叠加上。以下是您的代码中的主要问题以及正确代码中相应的解决方法：
1. 状态定义与初始化
您的代码中将状态 f[i][j] 定义为前 i 张票据，总金额不超过 j 时的最大金额。然而，您并未有效地处理票据间的日期差约束。而正确代码中，dp[i] 直接表示截至本年第 i 天所能报销的最大金额，这样的定义简化了问题的复杂度，更直接地反映了每一天的累积报销金额。
2. 日期映射与处理
您的代码尝试对每张票据进行处理，但对于满足日期差 K 天的条件的处理方式不正确。在正确代码中，通过映射函数 get_day 将所有日期映射到连续的天数，这简化了日期差 K 天的处理。每天的处理是基于之前 K 天的状态进行的，从而直接在 dp 数组中迭代更新，这种方法确保了对日期间隔的准确控制。
3. 动态规划迭代逻辑
在您的代码中，处理票据时只考虑了当前和上一个票据，而正确的处理方式应当查看前 K 天的累计金额。正确代码中，使用了 pre = max(0, i - k) 来定位从哪一天开始可以累加金额，从而确保了每次更新都符合日期差的要求。
4. 更新条件
正确代码中有一个关键的更新条件：if (dp[i] + dp[pre] <= m)，这确保了累加的总金额不超过 M。在您的代码中，这一点没有得到很好的处理，尤其是当多个票据在同一天时的处理。正确的代码通过每天的迭代来确保每一天的最大报销金额都是合法的。
5. 边界处理
正确代码确保了即使在年初或年末的边界条件下，也能正确处理累加金额的问题。而您的代码中对这种边界的处理不够明确。
总之，正确代码的核心在于将日期直接作为动态规划数组的索引，并且通过适当的迭代和条件判断来确保每一步的更新都是有效的，符合题目的要求。这种方法更加直接和高效地处理了日期间隔和金额限制的约束。
您当前的01背包问题的实现方式主要是在考虑如何选择一个项目（在这个案例中是票据），以及如何优化项目选择的组合来达到某个目标（最大化总报销金额而不超过给定限额）。然而，对于这个特定的问题，仅仅采用标准的01背包模型是不够的，因为有额外的约束条件——票据日期间的最小间隔K天。这个约束导致了几个实现上的挑战：
-
处理日期间隔的复杂性：在标准的01背包问题中，物品之间是相互独立的。但在这个问题中，每张票据是否可以选择，不仅取决于当前的费用限制（背包容量），还取决于之前选择的票据的日期。这需要一个方法来检查和保证任何两张票据之间的时间间隔至少为K天。
-
状态转移的依赖性：在您的代码尝试中，
f[i][j]的状态转移没有有效考虑到票据间的日期间隔。理论上，为了正确地应用日期间隔规则，您需要在考虑每张票据时，向前回溯查找所有可能的合法选择，而不仅仅是前一个或前K个。这意味着您的转移方程需要更复杂的逻辑来保证新加入的票据与所有已选票据的日期差满足要求。 -
优化的实现：由于日期的限制，即使两个解决方案的成本相同，它们也可能由于日期限制而不同。这需要您的DP实现能够灵活处理这种复杂性。
是否可行？
使用您的01背包方法理论上可行，但需要大幅修改以适应日期间隔的约束。特别是，您需要:
-
增强状态的定义：可能需要引入额外的维度或使用其他数据结构（如优先队列或有序集合）来追踪每个可能金额下的最后使用日期，以便您可以快速判断新的票据是否可添加。
-
复杂的状态转移：在选择每张票据时，您必须检查所有之前的日期，并确认是否存在任何符合间隔K天的日期。这可能会导致算法效率较低，因为您需要为每个票据检查多个可能的状态。
因此，虽然理论上可行，但实际实施时复杂度和所需的编程工作量会大大增加。考虑到这些因素，采用更直接的方法（如上面正确答案中的方法）通常更高效和容易实现。这样的方法直接在天数上进行动态规划，自然地融入了日期间隔的限制。
总之 分析得很接近了 真的可惜 这种题写起来确实有意思 但也真的很伤
代码实现
💬 评论